def maximumCostSubstring(s: str, chars: str, vals: list) -> int:
    """
    动态规划，O(n) 时间复杂度，最大子数组和思想
    """
    # 构建字符价值映射表
    value_map = {c: v for c, v in zip(chars, vals)}
    max_cost = 0
    curr = 0
    for ch in s:
        v = value_map.get(ch, ord(ch) - 96)  # 'a' = 97
        curr = max(v, curr + v)
        max_cost = max(max_cost, curr)
    return max_cost

if __name__ == "__main__":
    # 示例
    s = "adaa"
    chars = "d"
    vals = [-1000]
    print(maximumCostSubstring(s, chars, vals))  # 输出2
